
import copy
import time 
import util
import sys

sys.path.append('/usr/lib/pyshared/python2.7')
sys.path.append('/usr/local/lib/python2.7/dist-packages/')

from util import Queue
from util import Counter

from pygraph.classes.graph import graph
from pygraph.classes.digraph import digraph
from pygraph.algorithms.searching import breadth_first_search
from pygraph.algorithms import cycles

import pydot
import dot
import pygraphviz as gv



class LandMark:
    
    def __init__(self, relaxedGoops, state):
        self.relaxedGoops = [relaxedGoops]
        self.state = state
        self.startNodes = set()
        self.goalNodes = set()
        for goop in self.relaxedGoops[0]:
            "Only one loc--> the start point"
            self.goalNodes.add((goop, (-1,-1)))
            for loc in self.relaxedGoops[0][goop]:
                self.startNodes.add((goop, loc))

    def __repr__(self):
        iteration = 0
        firstRoundSeenIn = {}
        for relaxedGoop in self.relaxedGoops:
            continue
            print 'Iteration is %d\n' % iteration
            for goop in relaxedGoop:
                print "For goop ",  goop, " the possible moves are"
                for newLoc in relaxedGoop[goop]:
                    if iteration == 0: 
                        if newLoc == (-1,-1) and goop not in firstRoundSeenIn:
                            firstRoundSeenIn[goop] = iteration
                    else:
                        for start, preC in relaxedGoop[goop][newLoc]:
                            print "Move from ", start," to ",newLoc, " Pre ", preC 
                            if newLoc == (-1,-1) and goop not in firstRoundSeenIn:
                                #print "Goal! Move from ", start," to ",newLoc, " Pre ", preC 
                                firstRoundSeenIn[goop] = iteration
                            #print "Move from ", relaxedGoop[goop][newLoc]," to ",newLoc
            iteration += 1
        return '\n'
    
    def firstRoundSeenIn(self):
        iteration = 0
        firstRoundSeenIn = util.Counter()
        for relaxedGoop in self.relaxedGoops:
            for goop in relaxedGoop:
                for newLoc in relaxedGoop[goop]:
                    if iteration == 0: 
                        if newLoc == (-1,-1) and goop not in firstRoundSeenIn:
                            firstRoundSeenIn[goop] = iteration
                    else:
                        for start, preC in relaxedGoop[goop][newLoc]:
                            if newLoc == (-1,-1) and goop not in firstRoundSeenIn:
                                firstRoundSeenIn[goop] = iteration
            iteration += 1
        return firstRoundSeenIn
    
        
    def getLandMarks(self, initialState, boardNumber, graphics=False):
        goopExit = self.firstRoundSeenIn()
        'initialize goals'
        LGG = digraph()
        leaves = set()
        copyRelaxedGoops = copy.deepcopy(self.relaxedGoops)
        goops = { goop for goop in self.relaxedGoops[0]}
        goal = { goop : [(-1, -1)] for goop in self.relaxedGoops[0]}
        while len(copyRelaxedGoops) > 1:
            rround = copyRelaxedGoops.pop()
            for goop in rround: 
                for subGoal in goal[goop]:
                    'This is a klug need to handle initial states better'
                    if subGoal not in rround[goop]: continue
                    prevStateList = rround[goop][subGoal]
                    if (goop,subGoal) not in LGG: 
                        LGG.add_node((goop,subGoal), [("RPG",len(copyRelaxedGoops))])
                    elif (goop,subGoal) in leaves:
                        leaves.remove((goop,subGoal))
                    precondList = []
                    '''len(self.relaxedGoops) == goopExit[goop] mean the goop 
                    left this round of rpg'''
                    if ( (-1,-1) in rround[goop]  
                         and len(copyRelaxedGoops) == goopExit[goop]):
                        for fromLoc, precond in rround[goop][(-1,-1)]:
                            leaves.add((goop, fromLoc))
                            precondList.append(fromLoc)
                    goal[goop] = []
                    for pair in prevStateList:
                        fromLoc, precond = pair
                        if (goop, fromLoc) not in LGG and fromLoc != None: 
                            LGG.add_node((goop, fromLoc))
                            leaves.add((goop, fromLoc))
                            if precond != None: 
                                if precond not in LGG:
                                    LGG.add_node(precond,[("RPG",len(copyRelaxedGoops))])
                                    leaves.add(precond)
                                if not LGG.has_edge((precond, (goop, subGoal))):
                                    LGG.add_edge(( precond, (goop, subGoal) ),1, 'parent_ptr' )
                                    LGG.add_edge(( (goop, subGoal), precond ),1, 'child_ptr' )
                                    LGG.add_edge( ((goop, fromLoc), precond),1,'parent_ptr' )
                                    LGG.add_edge( (precond, (goop, fromLoc)),1,'child_ptr' )
                            else:
                                if not  LGG.has_edge(((goop, fromLoc), (goop, subGoal))):
                                    LGG.add_edge( ((goop, fromLoc), (goop, subGoal)),1,'parent_ptr' )
                                    LGG.add_edge( ((goop, subGoal), (goop, fromLoc)),1,'child_ptr' )
                            precondList.append(precond)
                        if fromLoc not in goal[goop]: goal[goop] += [fromLoc]
        for node in LGG.nodes():
            if len(LGG.node_neighbors[node]) == 0:
                LGG.del_node(node)
                if node in leaves:
                    leaves.remove(node)
        
        if graphics: 
            self.prettyGraphPicture(LGG, "1 Inital Landmarks_"+boardNumber, prog1='twopi')
        refinedLGG, refinedLeaves = self.removeUnprovableLandMarks(LGG, goops, leaves)
        if graphics:
            self.prettyGraphPicture(refinedLGG, "2 Landmarks after removing unprovable landmarks_"+boardNumber)
        self.getReasonableOrderingConstraints(refinedLGG, refinedLeaves)
        if graphics:
            self.prettyGraphPicture(refinedLGG, "3 Landmarks after reasonable orderings_"+boardNumber)
        self.getObedientOrderingConstraints(refinedLGG, refinedLeaves)
        if graphics:
            self.prettyGraphPicture(refinedLGG, "4 Landmarks after obedient resonable orderings_"+boardNumber)
        self.removeCycles(refinedLGG, refinedLeaves)
        if graphics:
            self.prettyGraphPicture(refinedLGG, "5 Landmarks after removing cycles_"+boardNumber)
        copyRefinedLeaves = copy.deepcopy(refinedLeaves)
        copyRefinedLGG = copy.deepcopy(refinedLGG)
        if graphics:
            self.prettyGraphPicture(copyRefinedLGG, "6 Landmarks after removing orphans_"+boardNumber)
        if graphics:
            self.prettyGraphPicture(copyRefinedLGG, "7 Landmarks after removing redundant leaves_"+boardNumber)
        return copyRefinedLGG, copyRefinedLeaves
    
    def prettyGraphPicture(self, g, filename, prog1='twopi', edgeTrim='child'):
        gString = dot.write(g, False)
        gvv = gv.AGraph(gString)
        for edge in gvv.out_edges():
            if edgeTrim == 'parent':
                if edge.attr['label'] == 'parent_ptr':
                    gvv.remove_edge(edge)
            elif edgeTrim == 'child':
                if edge.attr['label'] == 'child_ptr':
                    gvv.remove_edge(edge)
            else:
                pass
        gvv.layout(prog=prog1)
        try:
            gvv.draw(filename+'.jpeg', 'jpeg', prog=prog1,)
        except IOError:
            print "Error producing the graph "+filename    
        
    def trimRedundantLeaves(self, copyRefinedLeaves, LGG):
        leaves = copy.deepcopy(copyRefinedLeaves)
        count = { leaf[0]: 0 for leaf in copyRefinedLeaves}
        for leaf in copyRefinedLeaves:
            count[leaf[0]] +=1 
        for leaf in copyRefinedLeaves:
            guideValue = leaf[0]
            guideLeaf = leaf
            for leaf in copyRefinedLeaves:
                if( leaf[0] == guideValue and leaf != guideLeaf 
                    and count[guideValue] > 1 ):
                    leaves.remove(leaf)
                    LGG.del_node(leaf)
                    count[guideValue] -= 1
        return leaves
                    
    
    def removeCycles(self, refinedLGG, refinedLeaves):
        ''''
        TODO, but may not be necessary
        '''
        #print cycles.find_cycle(refinedLGG)
        pass
    
    def getObedientOrderingConstraints(self, refinedLGG, refinedLeaves):
        """
        This function imposes a obedient ordering on the LGG
        """
        for lPrime in refinedLGG.nodes():
            if lPrime not in self.goalNodes:
                for ln in refinedLGG.nodes():
                    if ln != lPrime and self.hasSameGNorRorder(refinedLGG, ln, lPrime):
                        for l in refinedLGG.nodes(): 
                            if self.hasPath(refinedLGG, l, ln):
                                if self.doesInterfere(refinedLGG, l, lPrime):
                                    self.addEdgeWithAttributes(refinedLGG,l, lPrime, "ob_reasonable")                      
                                    self.updateLeaves(refinedLeaves, refinedLGG, l, lPrime)
    
    def hasSameGNorRorder(self, refinedLGG, ln, lPrime):
        """
        In this check ln can have either a greedy n or reasonable path
        lPrime is just greedy n
        """
        if(refinedLGG.node_order(ln) == 0
           or refinedLGG.node_order(lPrime) == 0):
            return False
        for neig in refinedLGG.neighbors(ln):
            if refinedLGG.edge_label((ln, neig)) == 'parent_ptr':
                if (ln, neig) in refinedLGG.edge_attr:
                    if not (refinedLGG.edge_attr[(ln, neig)] == 'ob_reasonable'):
                        parentLn = neig
                    else:
                        return False
                else:
                    parentLn = neig
            else:
                return False
        for neig in refinedLGG.neighbors(lPrime):
            if refinedLGG.edge_label((lPrime, neig)) == 'parent_ptr':
                if (lPrime, neig) not in refinedLGG.edge_attr:
                    parentLPrime = neig
                else:
                    return False
            else: 
                return False
        return parentLn == parentLPrime
        
    def getReasonableOrderingConstraints(self, refinedLGG, refinedLeaves):
        """
        This function imposes a reasonable ordering on the LGG
        """
        for lPrime in refinedLGG.nodes():
            if lPrime in self.goalNodes:
                for l in refinedLGG.nodes(): 
                    if l != lPrime and self.doesInterfere(refinedLGG, l, lPrime):
                        if lPrime not in self.getPotentialGoalsfromNode(refinedLGG, l):
                            self.addEdgeWithAttributes(refinedLGG,l, lPrime, "reasonable")
                            self.updateLeaves(refinedLeaves, refinedLGG, l, lPrime)
            else:
                for ln in refinedLGG.nodes():
                    if ln != lPrime and self.hasSameGNorder(refinedLGG, ln, lPrime):
                        for l in refinedLGG.nodes():
                            if self.hasPath(refinedLGG, l, ln):
                                if self.doesInterfere(refinedLGG, l, lPrime):
                                    self.addEdgeWithAttributes(refinedLGG,l, lPrime, "reasonable")                      
                                    self.updateLeaves(refinedLeaves, refinedLGG, l, lPrime)
    
    def updateLeaves(self, leaves, refinedLGG, l, lPrime):
        """
        This function updates the leaves so that we can track which nodes are still
        considered leaves
        """
        if lPrime in leaves:
            leaves.remove(lPrime)
            if l not in leaves:
                leaves.add(l)
            return
        else: 
            return
                                    
    def hasPath(self, refinedLGG, l, ln):
        if refinedLGG.node_order(l) == 0: 
            return False
        s = util.Stack()
        s.push(l)
        explored = set()
        while not s.isEmpty():
            testNode = s.pop()
            if testNode == ln:
                return True 
            if testNode in explored: 
                continue
            for neig in refinedLGG.node_neighbors[testNode]:
                if refinedLGG.edge_label((testNode, neig)) == 'parent_ptr':
                    s.push(neig)
            explored.add(testNode)
        return False
    

    
    def hasSameGNorder(self, refinedLGG, ln, lPrime):
       
        if(refinedLGG.node_order(ln) == 0
           or refinedLGG.node_order(lPrime) == 0):
            return False
        
        for neig in refinedLGG.neighbors(ln):
            if refinedLGG.edge_label((ln, neig)) == 'parent_ptr':
                parentLn = neig
            else:
                return False
        for neig in refinedLGG.neighbors(lPrime):
            if refinedLGG.edge_label((lPrime, neig)) == 'parent_ptr':
                parentLPrime = neig
            else: 
                return False
        return parentLn == parentLPrime
    
    
    def addEdgeWithAttributes(self, LGG,l, lPrime, tag):
        if (l,lPrime) not in LGG.edges():                   
            LGG.add_edge((l,lPrime), [("tag", tag)])
        else:
            LGG.add_edge_attributes( (l, lPrime), [("tag", tag)] )
    
    def doesInterfere(self, refinedLGG, l, lPrime):
        """
        Check for landmark interference
        """
        '''Case 1 inconsistent landmarks, last boolean checks for prior
        greedy necessary link 
        '''
        if (l[0] == lPrime[0] and l != lPrime 
            and not refinedLGG.has_edge((l, lPrime))):
            return True
        '''Case 2 - 4: MAY NEED TO Troubleshoot later
        But essentially we are looking for cases where the landmarks before
        l (i.e. l's children) causes lPrime to be inconsistent or deleleted
        '''
        for neig in refinedLGG.neighbors(l):
            if refinedLGG.edge_label((l, neig)) == 'child_ptr':
                if neig[0] == lPrime[0] and neig != lPrime:
                    return True
        return False


    def getPotentialGoalsfromNode(self, refinedLGG, node):
        """
        Returns the set of final goals that a LM is related to 
        """
        testGoals = set()
        s = util.Stack()
        s.push(node)
        explored = set()
        while not s.isEmpty():
            testNode = s.pop()
            if testNode[1] == (-1,-1):
                testGoals.add(testNode)
                continue
            if testNode in explored: 
                continue
            for neig in refinedLGG.node_neighbors[testNode]:
                if refinedLGG.edge_label((testNode, neig)) == 'parent_ptr':
                    s.push(neig)
            explored.add(testNode)
        return testGoals

    def canTestGoalsReachLeaves(self, testLGG,testGoals, leaves):
        if len(testGoals) == 0: return False
        for goal in testGoals:
            ans = False
            s = util.Stack()
            s.push(goal)
            explored = set()
            while not s.isEmpty():
                testNode = s.pop()
                if testNode in leaves:
                    ans = True
                    continue
                if testNode in explored: 
                    continue
                for neig in testLGG.node_neighbors[testNode]:
                    if testLGG.edge_label((testNode, neig)) == 'child_ptr':
                        s.push(neig)
                explored.add(testNode)        
        return ans
    

    def removeUnprovableLandMarks(self, LGG, goops, leaves):
        '''
        Removes landmarks that cannot be proved from graph
        '''
        refinedLGG = copy.deepcopy(LGG)
        for node in LGG.nodes():
            if node[1] != (-1,-1) and node not in self.startNodes: 
                if(self.childCanReachGoalsWithOutLM(LGG, node)):
                    refinedLGG.del_node(node)
                    if node in leaves:
                        leaves.remove(node)
        return refinedLGG, leaves  
            
        
    def hasChildren(self, LGG, node):
        """
        Returns true or false if node has 
        """
        if len(LGG.neighbors(node)) == 0: return False
        for neig in LGG.neighbors(node):
            if LGG.edge_label((node, neig)) == 'child_ptr':
                return True
        return False

    def getNodeChildren(self, LGG, node):
        """
        Returns list of children 
        """
        ans = []
        if len(LGG.neighbors(node)) == 0: return []
        for neig in LGG.neighbors(node):
            if LGG.edge_label((node, neig)) == 'child_ptr':
                ans.append(neig)
        return ans
        
        
    def childCanReachGoalsWithOutLM(self, LGG, testLM):
        """
        This function checks to see if a child can reach a goal without 
        the parent == LM  
        """
        "Prune orphans! "
        for startNode in self.startNodes:
            "If any one goal canot be reached without LM then LM is provable"
            ans = False
            if startNode not in LGG: continue
            for neigh in LGG.neighbors(startNode):
                if neigh == testLM: return False 
                elif LGG.edge_label((startNode, neigh)) == 'parent_ptr': 
                    s = util.Stack()
                    s.push(neigh) 
                    explored = set()
                    ans = False
                    while not s.isEmpty():
                        testNode = s.pop()
                        if (testNode == (startNode[0],(-1,-1))):
                            ans =True
                            continue
                        if testNode in explored: continue
                        parentCount = 0
                        for succ in LGG.neighbors(testNode):
                            if (len(succ[0]) == 1):
                                if succ == testLM: 
                                    continue  
                            "Goop name is two char long"
                            if len(succ[0]) == 2: 
                                if succ[0][0] == testLM[0][0] and succ[1] == testLM[1]: 
                                    continue
                            if (LGG.edge_label((testNode, succ)) == 'parent_ptr'):  
                                s.push(succ)
                                parentCount += 1
                        explored.add(testNode)
                    if not ans: 
                        return False
        return ans
    
    
    
    
        
    def put(self, iteration, goop, newLoc, fromLoc, preCond):
        '''
        Puts values into the specificed RPG level 
        '''
        if len(self.relaxedGoops) <= iteration:
            #Initialize iteration
            self.relaxedGoops.append( {goop : {newLoc : [(fromLoc, preCond)]}} ) 
        else:
            thisRound = self.relaxedGoops[iteration]
            if goop not in thisRound: 
                thisRound[goop] = {newLoc : [(fromLoc, preCond)] } 
                return
            if (newLoc in thisRound[goop]):
                if(fromLoc not in self.getStartLocation(iteration, goop, newLoc) ):
                    'Then there is more than one move to get to that location'
                    thisRound[goop][newLoc].append((fromLoc, preCond))
                    return
                else:
                    "We did come from a previously seen location, now we check preconditions"
                    if(preCond not in self.getPreCond(iteration, goop, newLoc) ):
                        thisRound[goop][newLoc].append((fromLoc, preCond))
                    else:
                        'repeat move'
                        return
            else:
                'new Location!'
                thisRound[goop][newLoc] = [(fromLoc, preCond)]
                return
                
    def getStartLocation(self, iteration, goop, newLoc):
        thisRound = self.relaxedGoops[iteration]
        possibleLocations = thisRound[goop][newLoc]
        startList = []
        for loc, preCond in possibleLocations:
            startList.append(loc)
        return startList
    
    def getPreCond(self, iteration, goop, newLoc):
        thisRound = self.relaxedGoops[iteration]
        possiblePre = thisRound[goop][newLoc]
        startList = []
        for loc, preCond in possiblePre:
            startList.append(preCond)
        return startList
    
    def update(self):
        oldRound = self.relaxedGoops[len(self.relaxedGoops)-2]
        for goop in oldRound:
            for loc in oldRound[goop]: 
                if (oldRound[goop][loc] == (None, None)):
                    self.put(len(self.relaxedGoops)-1, 
                             goop, loc,  None, None)
                else:
                    for prevState, prec in oldRound[goop][loc]:
                        self.put(len(self.relaxedGoops)-1, 
                                 goop, loc,  prevState, prec)
                        
    
